#!/usr/env/bin python
# -*- coding: utf-8 -*-

# @Time    : 2020/12/20 10:42|10:42
# @Author  : yangdingyi
# @File    : 2020-12-20.316.去除重复字母
# @Software: PyCharm
from tools.my_methods import *


class Solution:
    def removeDuplicateLetters(self, s: str) -> str:
        # 1. 划水
        # # 先按字典排序
        # for a in sorted(set(s)):
        #     tmp = s[s.index(a):]
        #     # 看余下的是否能组成所需的字母
        #     if len(set(tmp)) == len(set(s)):
        #         return a + self.removeDuplicateLetters(tmp.replace(a, ""))
        # return ""
        # 2. ???
        # data = [0 for i in range(26)]
        # for si in s:
        #     data[ord(si) - ord('a')] += 1
        # return ''.join([chr(ord('a') + i) if data[i] > 0 else '' for i in range(26)])
        # 3.
        stack, vis, left = [], set(), defaultdict(lambda: 0)
        for si in s:
            left[si] += 1
        for si in s:
            if si not in vis:
                while stack and stack[-1] > si:
                    if left[stack[-1]] > 0:
                        ss = stack.pop()
                        vis.remove(ss)
                    else:
                        break
                stack.append(si)
                vis.add(si)
            left[si] -= 1
        return ''.join(stack)


questions = [
    ('bcabc',),
    ('cbacdcbc',),
]

work(questions, lambda q: Solution().removeDuplicateLetters(q[0]))
